package com.study;

import java.util.LinkedList;

//稀疏图， 邻接表
public class SparseGraph {
    private int v;  //节点数
    private int e;  //边数
    private boolean directed;   //边的方向
    private LinkedList<Integer>[] table;   //邻接表


    public int getV() {
        return v;
    }

    public int getE() {
        return e;
    }


    public SparseGraph( int v, boolean directed ){
        assert v > 0;

        this.v = v;
        this.directed = directed;
        this.e = 0;
        table = new LinkedList[v];

        for( int i = 0; i < v; ++i ){
            table[i] = new LinkedList<>();
        }
    }


    public void addEdge( int a, int b ){
        checkBound(a);
        checkBound(b);

        //先不处理平行边
        table[a].add(b);

        //如果是不同的点,并且是无向图的话，相互添加边
        if( a != b && !directed ){
            table[b].add(a);
        }
        e++;
    }

    //a->b 是否有边
    public boolean hasEdge( int a, int b ) {
        checkBound(a);
        checkBound(b);

        for( Integer i : table[a] ){
            if ( i == b ){
                return true;
            }
        }

        return false;
    }

    //返回 v 点的所有邻接点的迭代器
    public Iterable<Integer> adj( int v ){
        checkBound(v);

        return table[v];
    }

    //检查是否越界，越界抛出异常
    private void checkBound(int a ){
        if (a < 0 || a >= v ) {
            throw new ArrayIndexOutOfBoundsException("超过点的个数");
        }
    }




}
